package Top200;

import java.util.LinkedList;

/**
 * @author zhangmin
 * @create 2022-02-23 11:01
 */
public class insert57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n=intervals.length;
        if (n==0) return new int[][]{newInterval};
        LinkedList<int[]> res=new LinkedList<>();
        int i=0;
        while (i < n&&intervals[i][1]<newInterval[0]) {
            //区间无重叠
            res.add(intervals[i]);
            i++;
        }
        //区间有重叠
        while (i<n&&intervals[i][0]<=newInterval[1]){
            newInterval[0]=Math.min(intervals[i][0],newInterval[0]);
            newInterval[1]=Math.max(intervals[i][1],newInterval[1]);
            i++;
        }
        res.add(newInterval);
        while (i<n){
            res.add(intervals[i]);
            i++;
        }
        int[][] r=new int[res.size()][2];
        for (int j = 0; j < res.size(); j++) {
            r[j]=res.get(j);
        }
        return r;
    }
}
